1. Technical Field of the Invention
The present invention relates to receivers in a digital communications system, and more particularly to decoders for decoding non-binary convolutional coded data using a modified Viterbi algorithm.
2. Background of the Invention
FIG. 1 illustrates a typical digital communications system which includes a transmitter 12, receiver 14, and channel 24. The transmitter includes a channel encoder 16, multiplexer 18, modulator 20 and transmitter unit 22. The transmitter 12 may include other signal processing components which are not illustrated in FIG. 1, such as an encryption unit or frequency spreader in a code division multiple access (CDMA) system.
The channel encoder 16 in the transmitter 12 receives a source data signal and encodes the source data signal to improve the recovery of the signal by the receiver 14. One type of signal-space coding of digital data is M-ary signaling. The channel decoder transforms k data bits into one of M=2.sup.k symbols in the signal space. For binary data signals, k=1. One class of signal-space coding is the convolutional code which may be implemented with a K-stage shift register. At each unit of time, k bits are shifted into the first k stages of the register while bits already in the registers are shifted to the right by k stages. At each unit of time, the contents of selected shift registers are added, subtracted or otherwise manipulated to obtain a number n of coded bits. By shifting the k bits into the register at each unit of time, each shifted set of k bits specifies a transition to a limited number of permissible successor states in the encoder. As a result, the encoded bits represent not only the current state of the encoder but also indicate historical information of the states of the encoder which can be derived from the received sequence of the encoded bits.
The encoded bits from the channel encoder 16 are inputted into the multiplexer 18. The multiplexer 18 combines the encoded bits with other signals that originate from different sources or have different characteristics. The modulator 20 receives the multiplexed signal and converts the signal to waveforms that may be transmitted over the channel 24. The modulated signal is inputted to the transmitter unit 22 which typically includes a high powered amplifier and an antenna to transmit the modulated signal over the channel 24.
During transmission of the signal, the channel 24 introduces noise, fading and jamming into the signal. The receiver 14 must detect the transmitted signal and try to recover the original source data signal from the transmitted signal. The receiver 14 includes a receiver unit 26, demodulator 27, demultiplexer 28 and channel decoder 30. The receiver unit 26 typically includes an antenna to detect the transmitted signal and a low-noise amplifier to amplify the signal. The demodulator 27 demodulates the signal while the demultiplexer 28 separates the signal into component signals.
The channel decoder 30 attempts to decode the demultiplexed signal, with the added noise and fading, to reconstruct the original source data signal. One well known method for decoding convolutional codes is the Viterbi algorithm originated by A. J. Viterbi and described in the IEEE Transactions on Information Theory, Vol. IT-13, pp. 260-269 (April 1967), which is incorporated by reference herein. The Viterbi algorithm uses a trellis having columns of nodes that represent the possible states of the channel encoder 16 of the transmitter 12 and branches between nodes representing the allowed transitions between states. When the channel encoder only transitions one bit in a unit period of time, i.e. k=1, the trellis code is binary and has two associated branches per node. If the channel encoder transitions more than one bit in a unit time period, i.e. k&gt;1, then the trellis code is non-binary and has more than two associated branches per node.
Implementing a Viterbi algorithm for a non-binary trellis, i.e. a trellis with more than two branches per node, is much more complex than implementing a Viterbi algorithm for a binary trellis, i.e. a trellis with two branches per node because a significantly larger computational burden is placed on the channel decoder. This increased complexity has restricted the use of non-binary trellises for encoding and decoding data in commercial communications systems. Thus, a need has arisen in the industry for a simple and efficient method and decoder to perform decoding of convolutional codes using the Viterbi algorithm for a non-binary trellis.